回家再修文，先發ㄌ
晚點要補一下前一篇的 failure detectors

介紹分散式系統中的時間，主要分為

• physical clocks: count number of seconds elapsed
• logical clocks: count events, e.g. messages sent

這篇筆記在物理時間 3.1 3.2 不做太多著墨，
只需要知道因為誤差的關係，
分散式系統間的訊息傳遞不能以物理時間當作時戳，
否則可能會有時空旅行的可能。

3.3 會介紹邏輯時間的數學關係，以迎接第 4 章: Logical clock。

3.1 Physical clocks

對於分散式系統來說，物理時間較少使用。

• 石英 quartz clock: 便宜、不夠精確，容易因為溫度上升而失準。是現代電子錶最常使用的。
• atomic clock: 貴

UTC

根據 atomic 時間，但會依據地球自轉而有所校正。

GMT

leap seconds

校正 UTC 來大致符合地球自轉。
每年可能 +- 1 秒，會提前公告。
而這個東西會造成很大的問題！！
通常程式會直接忽略 leap seconds，對於一些系統來說這是很嚴重的事情。

leap second smearing

3.2 Clock synchronisation

• clock drift: 一個時鐘與精準時間的誤差
• clock skew: 兩個時鐘在某時刻的差距

如果兩個時鐘都有各自的 drift，那他們的 skew 隨著時間增加，所以需要 sync。
i.e. a時鐘慢了1秒，b時鐘快了1秒，每秒這兩個時鐘差就多2秒。

Network Time Protocol (NTP)

clock server 的層級：

• Stratum 0: atomic clock or GPS receiver
• Stratum 1: synced directly with stratum 0 device
• Stratum 2: servers that sync with stratum 1, etc.

Estimating time over a network

時間校正

根據 client 和 server 的時間差，調整 client 時鐘的策略有 3 種：

• slew: 加快或調慢一點點比例。
• step: 把 client 調為 server 時間。
• panic: 差異太大了，不做任何事，交給人解決。

Physical clock 主要分兩種，用錯麻煩多

Time-of-day clock

• 從固定日期開始計算的時間 (e.g. 1 January 1970 epoch)
• 可能突然增加或倒退（NTP stepping）
  因為 leap second 調整
• 不同 node 可用此 Timestamps 比較
  Java: System.currentTimeMillis()
  Linux: clock_gettime(CLOCK_REALTIME)

Monotonic clock

• 從 arbitrary point 開始計算的時間 (e.g. 從機器開機開始計時)
• 只會增加
  moves at a nearly constant rate
• Good for measuring elapsed time on a single node
  Java: System.nanoTime()
  Linux: clock_gettime(CLOCK_MONOTONIC)

Summary

所以單個電腦上要對某個動作計時，應該使用 monotonic clock。
如果是分散式系統，不得已得用 physical clock 來比較不同電腦的時間，則用 time-of-day clock。

3.3 Causality and happens-before

為什麼分散式系統上不能用物理時間？

再怎麼努力與 NTP sync，每個電腦上的物理時間還是有可能會有一點點誤差。
若以物理時間來重新排序訊息，一個不小心就可能時空旅行。
time skew > one way network delay?? 不太懂 3:27

happens-before

定義 happens-before relation
a -> b 代表 a happens-before b iff:

• a b 兩事件在同個 node 上發生，a 先執行，b 後執行。
• a b 兩事件在不同 node 上發生，a 是 n1 的傳送事件，b 是 n2 的接收事件。這應該很好理解。
• 遞移律：今天有的事件 c，a -> c，c -> b ，可以推得 a -> b。

happens-before 是個 partial order，
有可能 既不是 a -> b 也不是 b -> a，稱之 concurrent。
a || b。

什麼？為什麼可以不是 ａ－> b 也不是 ｂ-> a?

這可能小小的違反我們的直覺，
但 happens-before 關係是一種相對關係，
而我們直覺是基於物理時間的。

在分散式系統上，
如果不能使用物理時間，
那若沒有訊息傳遞，例如兩個 nodes 之間完全不聯繫，
我們無從去比較出兩個 node 上事件的 happens before relation 的。

concurrent 不代表 spontaneous！！
只是這兩個 events 不知道對方先發生還是後發生、無法比較而已。

• partial order: 能夠將一個 set 中的部分元素做排列
• total order: 能夠將一個 set 中的所有與素做排列

因果關係 Causality

happens-before relation 是一種可以討論分散式系統上事件之間因果關係的數學關係。

a -> b: a 可能 have caused b
a || b: a 不可能 have caused b

causal order
是代表
若 a causes b, then a happens before b?

似乎是從物理借鏡來的概念。
如果今天兩個事件發生的「距離夠遠」，就算時間很相近，但他們卻不會有關係，a 不可能影響 b。
分散式系統注重訊息的順序，其中也有同樣的概念，就是如果 a 跟 b 沒有 causal 關係的話，或許我們並不是很在意他們實際是不是在差不多的時間發生。
a || b : a 不可能 have caused b!